from typing import List


class Solution:
    """
    方法： threeSum

    逻辑:
    1. 对输入数组进行排序，以便使用双指针技术。
    2. 遍历数组，对于每个元素，使用双指针查找其余两个数，使得三数之和为零。
    3. 跳过重复的元素以避免重复的三元组。
    4. 使用双指针法缩小搜索范围，优化查找过程。

     Args:
        nums (List[int]): 输入的整数数组

     Returns:
        List[List[int]]: 返回所有符合条件的三元组列表，每个三元组由三个整数组成，且和为零

     Time:
        O(n^2)，其中 n 是数组长度。排序操作的时间复杂度是 O(n log n)，而双指针遍历操作的时间复杂度是 O(n^2)。

     Space:
        O(1)，不考虑返回结果所占用的空间，额外空间复杂度为常数级别。排序操作的空间复杂度取决于具体实现，通常为 O(log n) 到 O(n)。
    """
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        nums.sort()  # 对数组进行排序，以便后续使用双指针技术
        for i in range(n - 2):
            x = nums[i]
            # 跳过重复数字，避免重复的三元组出现
            if i > 0 and x == nums[i-1]:
                continue
            # 如果当前数字加上数组中接下来的两个数字之和大于0，则后续无需检查，直接跳出循环
            if x + nums[i + 1] + nums[i + 2] > 0:
                break
            # 如果当前数字加上数组中最大的两个数字之和仍小于0，则当前数字无法与其他数字组成和为0的三元组，跳过
            if x + nums[-2] + nums[-1] < 0:
                continue
            j, k = i + 1, n - 1  # 初始化双指针
            while j < k:
                s = x + nums[j] + nums[k]  # 计算当前三元组的和
                if s > 0:  # 和大于0，说明需要减小s的值，故将k指针左移
                    k -= 1
                elif s < 0:  # 和小于0，说明需要增大s的值，故将j指针右移
                    j += 1
                else:  # 找到一个和为0的三元组
                    ans.append([x, nums[j], nums[k]])
                    j += 1
                    k -= 1
                    # 移动指针，跳过重复的数字，避免重复的三元组
                    while j < k and nums[j] == nums[j-1]:
                        j += 1
                    while k > j and nums[k] == nums[k+1]:
                        k -= 1
        return ans
        